/********************************
 * Robinson Matrix Algorithm
 *
 * Copyright (C) 2009 CNRS
 * Author : Florent AVELLANEDA, Eugen CEPOI
 * 
 *
 * All rights reserved.
 *
 *   This file is part of Robinson Matrix Algorithm.
 *
 *   Robinson Matrix Algorithm is free software: you can redistribute it and/or modify
 *   it under the terms of the GNU General Public License as published by
 *   the Free Software Foundation, either version 3 of the License, or
 *   (at your option) any later version.
 *
 *   Robinson Matrix Algorithm is distributed in the hope that it will be useful,
 *   but WITHOUT ANY WARRANTY; without even the implied warranty of
 *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *   GNU General Public License for more details.
 *
 *   You should have received a copy of the GNU General Public License
 *   along with Robinson Matrix Algorithm.  If not, see <http://www.gnu.org/licenses/>.
 *
 ***********************************************************************************/
#ifndef UTIL_H_
#define UTIL_H_

#include <iostream>
#include <vector>
#include <set>
#include <string>

namespace Util
{
    template<class A>
        void afficherCollection(std::string s, A v)
        {
            std::cerr << s << " = ";
            for (typename A::iterator it = v.begin(); it != v.end(); ++it)
            {
                std::cerr << (*it) << ", ";
            }
            std::cerr << std::endl;
        }

    template<class A>
        std::vector<unsigned int> transformer( A &v, const std::vector<unsigned int> &t )
        {
            std::vector<unsigned int> result;
            result.reserve(v.size());
            for ( typename A::iterator it = v.begin(); it != v.end(); ++it )
                result.push_back(t[(*it)]);

            return result;
        }

    template<class A>
        void clear(A &v)
        {
            for ( typename A::iterator it = v.begin(); it != v.end(); )
            {
                delete (*it);
                v.erase(it);
            }
        }

    bool isAcyclique(std::vector< std::set<unsigned int> > &G);

    /** 
     * @brief calculate maximal chain
     * 
     * @param G graph
     * @param begin first node
     * @param end last node
     * @param result maximal chain
     * 
     * @return acyclique||no solution ? true : false;
     */
    bool calculateMaximalChain( std::vector< std::set<unsigned int> > &G, unsigned int begin, 
            unsigned int end, std::vector<unsigned int> &result );

    bool calculateMaximalChain( std::vector< std::set<unsigned int> > &G, std::vector<unsigned int> &result );

    /** 
     * @brief recursion for calculate maximal chain
     * 
     * @param G graph
     * @param noeud curent node
     * @param val curent distance
     * @param gris all node gris
     * @param prec array for save path
     * @param dist array for save distance
     * 
     * @return 
     */
    bool maximalChainRec( std::vector< std::set<unsigned int> > &G, unsigned int noeud, 
            unsigned int val, std::set<unsigned int> &gris, std::vector<unsigned int> &prec, 
            std::vector<unsigned int> &dist );

    std::vector<unsigned int> notIn( std::set<unsigned int> &elements, std::vector<unsigned int> &vect);

    double dabs(double a);
    double max( double a, double b);
    double min( double a, double b);
};

#endif /*UTIL_H_*/
